package com.sort;

public class HeapSort {
    public void sort(int[] arr){
        //创建堆
        for(int i=(arr.length-1)/2;i>=0;i--){
            //从第一个非叶子结点从上至下，从左至右调整结构
            adjustHeap(arr,i,arr.length);
        }
        //调整堆结构和交换堆顶元素与末尾元素
        for(int i=arr.length-1;i>0;i--){
            //交换堆顶元素与末尾元素
            int tmp = arr[i];
            arr[i] = arr[0];
            arr[0] = tmp;
            //重新调整堆结构
            adjustHeap(arr,0,i);
        }
    }
//    大顶堆，升序排序
    public void adjustHeap(int[] arr,int parent,int length){
        int tmp = arr[parent];
        int lChild = parent*2+1;
        while(lChild<length){
            int rChild = lChild+1;
            //如果有右孩子结点，并且右孩子结点的值大于左孩子，则选取右孩子结点
            if(rChild<length && arr[lChild]<arr[rChild]){
                lChild++;
            }
//            如果父结点的值大于孩子结点的值，则直接结束，
            if(tmp>=arr[lChild]) break;
//            否则把孩子结点的值给父节点
            arr[parent] = arr[lChild];
//            选取孩子结点的左孩子结点，继续向下筛选
            parent = lChild;
            lChild = 2*parent+1;
        }
        arr[parent] = tmp;
    }
//    小顶堆，降序排序
    public void adjustHeap2(int[] arr,int parent,int length){
        int tmp = arr[parent];
        int lChild = parent*2+1;
        while(lChild<length){
            int rChild = lChild+1;
            //如果有右孩子结点，并且右孩子结点的值大于左孩子，则选取右孩子结点
            if(rChild<length && arr[lChild]>arr[rChild]){
                lChild++;
            }
//            如果父结点的值大于孩子结点的值，则直接结束，
            if(tmp<=arr[lChild]) break;
//            否则把孩子结点的值给父节点
            arr[parent] = arr[lChild];
//            选取孩子结点的左孩子结点，继续向下筛选
            parent = lChild;
            lChild = 2*parent+1;
        }
        arr[parent] = tmp;
    }
}
